COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Directory of cs254 files
C00021 ENDMK
C⊗;
Directory of cs254 files
 
\leftline{\sevenrm B01.tex[254,mps]\today}
\noindent{\bf Composition of Machines and Programs} [will replace A65]
 
Actually A01 
 
\line{\sevenrm a02.tex[154,mps] \today\hfill}
A {\it context-free grammar\/} (CFG) $G$ is a system for defining a
language over~$\Sigma↓G$. It uses a finite alphabet $V↓G$ which is
an extension of~$\Sigma↓G$; we define $N↓G=V↓G-\Sigma↓G$. It has a
 
\line{\sevenrm a03.tex[154,mps] \today\hfill}
\noindent{\bf Earley's Algorithm for Context-Free Language Recognition
and Parsing}

\line{\sevenrm a10.tex[154,mps] \today\hfill}
There are inherently ambiguous context-free languages.
 
\leftline{\sevenrm A11.Tex[154,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, February 3, 1989}
\noindent{\bf Regular Expressions for FALs}
 
\line{\sevenrm a15.tex[254,mps] \today\hfill}
\line{\copyright July 6, 1984 Robert W. Floyd\hfill}
{\bf Cartesian Products and Ordered Pairs.}
[This note was prepared by gluing three separately written ones together.
Redundancies abound. Sorry.]
 
\line{\sevenrm a34.tex[154,mps] \today\hfill}
\line{\bf Ogden's (alias Pumping, alias $uvwxy$) Theorem\hfill}
 
\line{\sevenrm a39.tex[154,mps] \today\hfill}
\line{\bf The Relation Between Stacks and Parentheses\hfil}
 
\line{\sevenrm a45.tex[154,mps] \today\hfill}
\line{\bf Ambiguity\hfil}
 
\leftline{\sevenrm A64.Tex[254,rwf]\today}
\noindent{\bf Nondeterministic Machines\hfill}
 
\leftline{\sevenrm A65.Tex[254,rwf]\today}
\noindent{\bf Determinacy-Preserving Composition\hfill}
 
\leftline{\sevenrm A66.tex[254,mps]\today}
\noindent{\bf Chapter 2: Definition of machine, standardize, simulate, \dots\hfil}

\leftline{\sevenrm A67.tex[254,mps]\today}
\noindent{\bf Examples of Machine Simulations}
 
\line{\sevenrm a68154.tex \today\hfill}
\noindent{\bf Equivalence in Languages}

\leftline{\sevenrm a69.tex[254,mps]\today}
\noindent{\bf Standardizing a DPDM}
 
\leftline{\sevenrm A70.Tex[254,MPS]\today}
\noindent{\bf Undecidability of the Halting Problem, Oblivious Programs, and
Rice's Theorem}
 
\leftline{\sevenrm A71.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 7, 1988}
\noindent{\bf Definitions of Acceptance, Recognition, and Simulation}
 
\leftline{\sevenrm A72.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 14, 1988}
\noindent{\bf Undecidability of First-order Predicate Calculus}

\leftline{\sevenrm A73.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 22, 1988}
\noindent {\bf Acceptors, Recognizers, and Classifiers}

\leftline{\sevenrm A74.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 22, 1988}
\noindent{\bf The Partition Theorem}
 
\leftline{\sevenrm A75.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 6, 1988}
\noindent{\bf The Post Correspondence Problem}
 
\leftline{\sevenrm A76.Tex[254,mps]\today}
\leftline{\copyright \sevenrm Robert W. Floyd, November 30, 1988}
\noindent{\bf Notes on NP-Completeness}
 
\leftline{\sevenrm A77.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\noindent{\bf Proofs for Takehome Final, CS 254, Spring 1985--86}
 
\leftline{\sevenrm A78.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\noindent{\bf Solutions to some takehome final problems}
 
\leftline{\sevenrm A79.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\noindent{\bf Final Exam -- Part I. June 10, 1986}
 
\leftline{\sevenrm A80.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\noindent{\bf Final Exam -- Part I. Closed book. Autumn 1984}
 
\leftline{\sevenrm A81.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, August 28, 1989}
\noindent{\bf The Decomposition Theorem for CFGs}
 
\leftline{\sevenrm A83.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 12, 1988}
\noindent {\bf Least Fixed Points}
 
\leftline{\sevenrm A84.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, January 12, 1989}
Take any locally constrained symbol system with $k$ variables, and $m$
constraints that apply to subsets of at most $b$ variables.  There are at
most ${k\choose b}$ such subsets, a polynomial of degree $b$.  The
 
\leftline{\sevenrm A85.Tex[254,rwf]\today}
\leftline{\copyright Robert W. Floyd, January 30, 1989}
[Rough draft of theorem on D1CLs]
Let $L$ be a language.  Let $e↓n$ be the number of distinct prefix equivalence
classes of prefixes of length $n$.  We show if $e↓n/n$ is unbounded, no
D1CA accepts $L$.  Suppose some D1CA does accept $L$.
 
\leftline{\sevenrm A86.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, January 31, 1989}
\noindent {\bf 1.  EXAMPLES}
\noindent {\bf 1.1  Finite automata}
The simplest machine that we consider has only one device, a finite
memory.  This kind of machine is called a {\it finite automaton (FA)}.
 
\leftline{\sevenrm A87.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 7, 1989}
Let $\langle x↓1, x↓2\rangle$ be the ordered pair with first element $x↓1$ and
second element $x↓2$.  Correspondingly, there are two {\it projection}
functions $h$ and $t$ (head and tail) for which $\langle x↓1, x↓2\rangle 
h = x↓1$ and $\langle x↓1, x↓2\rangle t = x↓2$.
 
\leftline{\sevenrm A88.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 13, 1989}
Consider a machine $M$ with an input device, a Turing memory device, and an
oracle for an arbitrary set $A$.  Let $H(u,v)$ be the predicate: $M$, with
program $u$, and with input $v$, halts.  If there were an algorithm
 
\leftline{\sevenrm A89.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 18, 1989}
A {\it relation from} $R$ {\it to} $S$ is a subset of $R \times S$, i.e.
a set of ordered pairs $\langle r,s\rangle$ with $r\in R$, $s\in S$.  Relations
will be named by lower case Greek letters.  A relation can be exhibited by
its {\it graph}: a figure with a point for each member of $R\cup S$, and an
 
\leftline{\sevenrm A90.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 19, 0989}
A relation $\sigma$ is {\it concatenative} if $x↓1\sigma y↓1$ and $x↓2\sigma y↓2$ 
implies $(x↓1x↓2)\sigma (y↓1y↓2)$.
 
\leftline{\sevenrm A91.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 20, 1989}
Let $M$ be a machine $\langle$control, input, other$\rangle$ and $\pi$ a program
for it, using the maximum input repertory.  We construct a program $\pi'$ for
$M$ that simulates $\pi$, using the minimum input repertory.  That is,
$\pi'$ omits {\tt next a}, and never even considers an input operation after
 
\leftline{\sevenrm A92.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 22, 1989}
{\bf Theorem:}  The set of strings of composite length is not a CFL.
 
\leftline{\sevenrm A93.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 27, 1989}
\noindent {\bf Reflexive Transitive Closures}
 
\leftline{\sevenrm A94.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 29, 1989}
\noindent{\bf Example for CS254:  composites (in unary) are not pumpable.}
 
\leftline{\sevenrm A95.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 2, 1989}
\noindent{\bf Primitive Recursion [Uses list convention]}
 
\leftline{\sevenrm A96.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 22, 1988}
\noindent {\bf Acceptors, Recognizers, and Classifiers}
 
\leftline{\sevenrm A97.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 6, 1989}
{\bf Theorem:}  There is no algorithm which for every program $x$ and 
datum $d$, determines whether or not $x$ halts when presented with $d$.
(Crude draft)
 
\leftline{\sevenrm A98.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 13, 1989}
Let $A$ be any set, $M$ a Turing machine with an A-oracle.  Let predicate 
$H(c, d)$ be true iff $c$ encodes a program for $M$ that accepts argument $d$.  
We show that no program for $M$ can compute $H$.
 
\leftline{\sevenrm A99.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 1, 1989}
\noindent{\bf Notes on NP-Completeness.\hfill}
A locally constrained symbol system (LCSS) consists of a finite set
 
\leftline{\sevenrm B01.tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, May 1988}
\noindent{\bf Composition of Machines and Programs} [will replace A65]

Below are files from [154,rwf]

A01  Not All Languages are FMLs
A02  A context-free grammar (CFG) 
A03  Earley's Algorithm for Context-Free Language Recognition and Parsing
A04  Transitivity is not a decidable property of recursive relations.
A05  Unsolvability of Formal Language Problems
A06  A function .. from sets to sets is monotone if
A07  Quantifiers, Universal and Existential.
A08  The Partition Theorem
A09  To ``standardize'' a PDA, constructed as a flowchart 
A10  Theorem. There are inherently ambiguous context-free languages.
A11  Regular Expressions for FALs
A12  midterm and final for Spring 1984
A13  String Axioms.
A14  The natural numbers are defined by:
A15  Cartesian Products and Ordered Pairs.

A17  A Sufficiency of Fallacies.
A18  An Example of an Epsilon-Delta Proof
A19  Congruence modulo $m$.
A20  Exercise: Show the following are equivalent for deterministic finite
     automata:
A21  (2) Exercise: In the graph with nodes .. the edges, labeled, are:
A22  Exercise: In the regular expression .. number of paths 
A23  [Subject: Pairing functions, sequences.]
A24  Proofs by induction about summations of polynomial functions,
A25  If C is a class of machines (e.g., deterministic machines with finitely
A26  Theorem: Any (partial) function that can be computed
A27  A context-free grammar (CFG) G is a system for defining a language
A28  Greibach's Theorem

A30  Given a DFA, to test strings, x and y for prefix equivalence.
A31  Midterm solutions.
A32  Equivalence and Minimization of Deterministic Finite Automata
A33  set functions
A34  Ogden's Pumping $uvwxy$ Theorem
A35  Semigroups.
A36  Primitive Roots.
A37  Moore machine:
A38  If L is a language over .. ,  two equivalence relations
A39  The Relation Between Stacks and Parentheses
A40  Context-free Languages as Fixed Points
A41  Midterm Spring 1986
A42  Homework Solution. See Hopcroft and Ullman, Ex.~3.20.
A43  Solution to Hopcroft and Ullman, Exercise 1.4 (Revised).
A44  Midterm With Some Solutions .. Spring 1986
A45  Ambiguity
A46  Pairing Functions 
A47  Rice's Theorem 
A48  Factoring Input-Output Relations 
A49  Homorphisms
A50  Proofs for Takehome Final, CS 254, Spring 1985--86
A51  Solutions to some takehome final problems
A52  Homework - CS 254 - to be exercises or examples.
A53  PROBLEMS FOR THE FORMAL LANGUAGE BOOK
A54  Final Exam -- Part I. June 10, 1986
A55  Final Exam -- Part I. Closed book. Autumn 1984
A56  The Hennie-Stearns Theorem
A57  Transitive Closures
A58  Kleene's Theorem and Digraphs
A59  Finite Fields and Primitive Roots
A60  The First-order Calculus is Undecidable --- Short Proof
A61  Primitive Recursion
A62  Fixed Point Theory
A63  Machines and Computations
A64  Nondeterministic Machines
A65  Determinacy -- Preserving Composition
A66  Chapter 2: Definition of machine, standardize, simulate, ...
A67  Standardizing a finite machine
A68  Equivalence in Languages